import java.util.Random;


public class Main {
	public static void main(String args[]){
		ListaSimple ls = new ListaSimple();
		ls.annadirPrincipio(8);
		ls.annadirPrincipio(7);
		ls.annadirPrincipio(6);
		
		
		ls.annadirPrincipio(6);
		ls.annadirPrincipio(7);
		ls.annadirPrincipio(8);
		
		
		System.out.println(ls.esPalindrome());
		/*
		ls.imprimeLista();
		
		ListaSimple ls1= new ListaSimple();
		ls1=ls.invertirListaIterativo();
		System.out.println("INVERTIDO ITERATIVO");
		ls1.imprimeLista();
		
		ListaSimple ls2= new ListaSimple();
		ls2=ls.invertirListaRecursivo();
		System.out.println("INVERTIDO Recursivo");
		ls2.imprimeLista();
		*/
		
		
		/*
		Main objeto= new Main();
		long inicio=0, termina=0;
		int tamVector=1000000;
		int vector[]=new int[tamVector];
		vector= objeto.llenaVector();
		int ran=(int)((tamVector)*Math.random())+1;
		int num= vector[5000];
		
		
		inicio=System.nanoTime();
		System.out.println("Buscar secuencial: "+objeto.busquedaSecuencial(vector, num));
		termina=System.nanoTime();
		System.out.println("secuencial "+(termina-inicio)+" ms");
		
		inicio=System.nanoTime();
		System.out.println("Buscar secuencial recursiva: "+objeto.busquedaSecuencialRecursiva(vector, num));
		termina=System.nanoTime();
		System.out.println("secuencial "+(termina-inicio)+" ms");
		
		inicio=System.nanoTime();
		System.out.println("Buscar binario: "+objeto.busquedaBinaria( vector, num));
		termina=System.nanoTime();
		System.out.println("Iterativo "+(termina-inicio)+" ms");
		
		inicio=System.nanoTime();
		System.out.println("Buscar binarioRecursivo: "+objeto.busquedaBinariaRecursiva(vector, num));
		termina=System.nanoTime();
		System.out.println("Recusivo "+(termina-inicio)+" ms");
		*/
		/*Potencias
		*inicio=System.currentTimeMillis();
		System.out.println("Elevar potencias iterativa: "+objeto.elevarPotenciasIterativo(20, 10));
		termina=System.currentTimeMillis();
		System.out.println("Iterativo "+(termina-inicio)+" ms");
		
		inicio=System.currentTimeMillis();
		System.out.println("Elevar potencias RCola: "+objeto.elevarPotenciasRecurcionCola(20, 10));
		termina=System.currentTimeMillis();
		System.out.println("RCola "+(termina-inicio)+" ms");
		
		inicio=System.currentTimeMillis();
		System.out.println("Elevar potencias RPila: "+objeto.elevarPotenciasRecurcionPila(20, 10));
		termina=System.currentTimeMillis();
		System.out.println("RCola "+(termina-inicio)+" ms");
		*/
		
		/*Division por restas
		*inicio=System.currentTimeMillis();
		System.out.println("Division iterativa: "+objeto.divisionPorRestaIterativo(30000, 7));
		termina=System.currentTimeMillis();
		System.out.println("Iterativo "+(termina-inicio)+" ms");
		
		inicio=System.currentTimeMillis();
		System.out.println("Division recursiva por cola: "+objeto.divisionPorRestaRecurcivoCola(30000, 7));
		termina=System.currentTimeMillis();
		System.out.println("Cola recurcion "+(termina-inicio)+" ms");
		
		inicio=System.currentTimeMillis();
		System.out.println("Division recursiva por pila: "+objeto.divisionPorRestaRecurcivoPila(30000, 7));
		termina=System.currentTimeMillis();
		System.out.println("pila "+(termina-inicio)+" ms");*/
		
		
		/*FIBONNACI
		 * long inicio=System.currentTimeMillis();
		System.out.println("Numero Iterativo: "+objeto.fibonnaciIterativo(20));
		long termina=System.currentTimeMillis();
		System.out.println("Iterativo "+(termina-inicio)+" ms");
		inicio=System.currentTimeMillis();
		System.out.println("Numero recurcion por cola: "+objeto.fibonnaciRecurcionCola(20));
		termina= System.currentTimeMillis();
		System.out.println("Recursivo cola "+(termina-inicio)+" ms");
		inicio=System.currentTimeMillis();
		System.out.println("Numero recurcion por pila: "+objeto.fibonnaciRecurcionPila(20));
		termina= System.currentTimeMillis();
		System.out.println("Recursivo pila "+(termina-inicio)+" ms");*/
		
	}
	
	//O(n)
	public long fibonnaciIterativo(long n){
		n--;
		long primero=0;
		long segundo=1;
		long resultado=0;
		for(long i=0;i<n;i++){
			resultado=primero+segundo;
			primero=segundo;
			segundo=resultado;
			
		}
		return resultado;
	}
	
	//O(n)
	public long fibonnaciRecurcionCola(long n){
		n--;
		return fibonnaciRCola(0, 1, n);
	}
	
	private long fibonnaciRCola(long primero,long segundo, long n){
		if(n==0){
			return segundo;
		}else{
			n--;
			return fibonnaciRCola(segundo, (segundo+primero), n);
		}
	}
	
	//O(2^n)
	public long fibonnaciRecurcionPila(long n){
		if(n==0||n==1){
			return n;
		}else{
			return fibonnaciRecurcionPila(n-1)+fibonnaciRecurcionPila(n-2);
		}
	}
	
	//O(n)
	public long divisionPorRestaIterativo(long dividendo,long divisor){
		int cociente=0;
		
		while(dividendo>=divisor){
			cociente++;
			dividendo-=divisor;
		}
		return cociente;
	}
	
	public long divisionPorRestaRecurcivoCola(long dividendo,long divisor){
		return divisionPorRestaRCola(dividendo, divisor, 0);
	}
	
	private long divisionPorRestaRCola(long dividendo, long divisor, long contador){
		if(dividendo<divisor){
			return contador;
		}else{
			contador++;
			return divisionPorRestaRCola(dividendo-divisor, divisor, contador);
		}
	}
	
	public long divisionPorRestaRecurcivoPila(long dividendo, long divisor){
		if(dividendo<divisor){
			return 0;
		}else{
			return 1+divisionPorRestaRecurcivoPila(dividendo-divisor, divisor);
		}
	}
	//O(Log n)
	public double elevarPotenciasIterativo(long num, long potencia){
		long m=potencia;
		double q=num;
		double p=1;
		while(m>0){
			if(m%2!=0){
				p*=q;
			}
			m/=2;
			q*=q;
		}
		return p;
	}
	//O(Log n)
	public double elevarPotenciasRecurcionCola(long num, long potencia){
		
		return elevarPotenciaRCola(num, potencia, 1);
	}
	
	private double elevarPotenciaRCola(long num, long potencia, long cont){
		if(potencia==0){
			return cont;
		}else{
			if(potencia%2!=0){
				cont*=num;
			}
			potencia/=2;
			num*=num;
			return elevarPotenciaRCola(num, potencia, cont);
		}
		
	}
	
	//O(n)
	public double elevarPotenciasRecurcionPila(long num, long potencia){
		if(potencia==0){
			return 1;
		}
		else{
			potencia--;
			return num*elevarPotenciasRecurcionPila(num, potencia);
		}
	}
	final int tamanno= 1000000;
	public int[] llenaVector(){
		int vector[]= new int[tamanno];
		vector[0]=(int)((10)*Math.random())+1;
		for(int i=1;i<tamanno;i++){
			vector[i]=vector[i-1]+((int)((10)*Math.random())+1);
		}
		
		return vector;
	}
	
	 public int busquedaBinaria( int [] arreglo, int dato) {
		    int inicio = 0;
		    int fin = arreglo.length - 1;
		    int pos;
		    while (inicio <= fin) {
		        pos = (inicio+fin) / 2;
		        if ( arreglo[pos] == dato )
		            return pos;
		        else if ( arreglo[pos] < dato ) {
		            inicio = pos+1;
		        }
		        else {
		    fin = pos-1;
		        }
		    }
		 return -1;
	}
	 public int busquedaBinariaRecursiva(int [] arreglo, int dato){
		 return busquedaBinariaR(0, 0, tamanno-1, arreglo, dato);
	 }
	 private int busquedaBinariaR(int pos, int inicio, int fin,int arreglo[], int dato){
		 if(inicio<=fin){
			 pos=(inicio+fin)/2;
			 if(arreglo[pos]==dato){
				 return pos;
			 }else if(arreglo[pos]<dato){
				 return busquedaBinariaR(pos, ++pos, fin, arreglo, dato);
			 }else{
				 return busquedaBinariaR(pos, inicio, --pos, arreglo, dato);
			 }
		 }
		 return -1;
	 }
		
	
	public int busquedaSecuencial(int vector[], int b){
		for(int i=0; i<tamanno; i++){
			if(vector[i]==b){
				return i;
			}
		}
		return -1;		
	}
	public int busquedaSecuencialRecursiva(int vector[], int b){
		return busquedaSecuencialR(vector, b, 0);
	}
	private int busquedaSecuencialR(int vector[], int b, int cont){
		if(cont<tamanno){
			if(vector[cont]==b){
				return cont;
			}
			else{
				return busquedaSecuencialR(vector, b, ++cont);
			}
		}
		
		return -1;
	}
	
}
